package com.simon.study.algorithm.collect;

import com.alibaba.fastjson.JSON;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import lombok.Getter;
import lombok.ToString;
import lombok.var;
import org.junit.Test;

/**
 * <p>
 *
 * @author simon
 * @date 2021/10/5 10:00 上午
 */
public class ManacherList {

    public static char[] manacherString(String str){
        char[] cs = str.toCharArray();
        char[] res = new char[cs.length*2+1];

        int index = 0;
        for(int i=0; i < res.length; i++){
            res[i] = (i&1) == 0 ? '#' : cs[index++];
        }

        return res;
    }


    public static int manacher(String str){
        char[] sc = manacherString(str);

        int[] pArr = new int[sc.length];

        int c=-1, r = -1, max = 0;

        for(int i=0; i<sc.length; i++){
            pArr[i] = r > i ? Math.min(pArr[2*c-i], r-i) : 1;

            while (i+pArr[i]<sc.length && i-pArr[i] > -1){
                if(sc[i+pArr[i]] == sc[i-pArr[i]]) {
                    pArr[i]++;
                }else {
                    break;
                }
            }

            if(i+pArr[i] > r){
                c = i;
                r = i+pArr[i];
            }
            max = Math.max(max, pArr[i]);
        }

        return max-1;
    }


    @Test
    public void increasingStackTest() {
        int[] arr = {3,6,5,2,7,9,4,8,1};
        var dd = increasingStack(arr);

        System.out.println(JSON.toJSONString(dd));
    }



    public static List<ComparisonInfo> increasingStack(int[] arr){
        Deque<Integer> deque = new ArrayDeque<>();
        Map<Integer, ComparisonInfo> cimap = new HashMap<>();
        int next = 0; deque.push(next++); boolean notExceed = true;

        while (!deque.isEmpty()){
            if(next>arr.length-1){ notExceed = false; }

            Integer cur = deque.peekFirst();
            while(cur != null && (!notExceed || arr[cur]<arr[next])){
                cur = deque.pollFirst();

                var info  = getInfo(arr, cur, cimap);
                if(notExceed) {
                    info.rightMaxIdx = next;
                    info.rightMax = arr[next];
                }

                cur = deque.peekFirst();

                if(cur != null){
                    info.leftMax    = arr[cur];
                    info.leftMaxIdx = cur;
                }
            }

            if(notExceed){ deque.push(next++); }
        }

        return new ArrayList<>(cimap.values());
    }


    public static ComparisonInfo getInfo(int[] arr, Integer idx, Map<Integer, ComparisonInfo> cimap){
        ComparisonInfo curInfo = cimap.get(idx);
        if (curInfo == null) {
            curInfo = new ComparisonInfo();
            curInfo.idx = idx;
            curInfo.value = arr[idx];
            cimap.put(idx, curInfo);
        }
        return curInfo;
    }

    @ToString
    @Getter
    public static class ComparisonInfo{
        Integer value;
        Integer idx;
        Integer leftMax;
        Integer leftMaxIdx;
        Integer rightMax;
        Integer rightMaxIdx;
    }


}
